package com.sunny.l63;

public class Solution {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(2);
        node1.next = node2;
        node2.next = node3;

        Solution solution = new Solution();
        solution.print(solution.partition(node1,3));

    }

    public void print(ListNode list){
        ListNode node = list;
        while (null != node){
            System.out.println(node.val);
            node = node.next;
        }
    }

    public ListNode partition(ListNode head, int x) {

        if(null == head)
            return head;

        if(head.val < x){
            ListNode prev = head;
            ListNode node = head;
            while (null != node.next){
                ListNode bak = node.next;
                if(node.next.val < x){
                    ListNode tmp = node.next;
                    node.next = node.next.next;
                    tmp.next = prev.next;
                    prev.next = tmp;
                    prev = prev.next;
                }
                node = bak;
            }
            return head;
        }else{
            ListNode node = head;
            while (null != node.next){
                if(node.next.val < x){
                    ListNode tmp = node.next;
                    node.next = node.next.next;
                    tmp.next = head;
                    head = tmp;
                    break;
                }
                node = node.next;
            }
            if(head.val < x)
                return partition(head, x);
            return head;
        }

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}